package label_setting_algorithm_VRPTW;

import java.util.ArrayList;

/**
 * https://mp.weixin.qq.com/s/7Q1R98BGsyygpm9kcYSoQQ
 * readme.txt
 */
public class Label_Setting {
    public static int n; // 节点个数
    public static int[][] cost; // 点与点之间的距离矩阵（编号从1开始）
    public static int[][] time; // 点于点之间的时间矩阵（编号从1开始）
    public static ArrayList<Label> labels = new ArrayList<>();

    // 其中P.get(i)表示从出发点到达i点的最短路径，P.get(i).get(j)表示从出发点到i点的最短路径中的第j个节点。Q亦然
    public static ArrayList<ArrayList<Label>> Q; // Q标号，永久标记
    public static ArrayList<ArrayList<Label>> P; // P标号，已处理集合
    public static ArrayList<Label> T = new ArrayList<>(); // 未处理点集合（当前未处理，且下一步可处理的点）
    // Q.get(i)存储的是所有到达i的节点，顺序从优到劣排列

    public static void main(String[] args) {
        // 1.初始化算例
        init();

        // 2.寻找初始的T标号集合
        boolean flag = buildT();

        while (flag) {
            Label l = min_label();
            // System.out.print("标号：");
            // System.out.println(l.toString());
            treatable(l);
            flag = buildT();
        }

        // 3.输出解
        System.out.println("最终解：");
        for (int i = 1; i <= n; i++) {
            Label l = P.get(i).get(P.get(i).size() - 1);
            while (true) {
                System.out.print(l.getId() + "<-");
                if (l.getI() == -1 && l.getJ() == -1) {
                    break;
                }
                l = P.get(l.getI()).get(l.getJ());
            }
            System.out.println();
        }
    }

    // 初始化算例和标号点
    public static void init() {
        n = 4;
        // 1.初始化距离矩阵和成本矩阵
        cost = new int[n + 1][n + 1];
        time = new int[n + 1][n + 1];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                cost[i][j] = Integer.MAX_VALUE;
                time[i][j] = Integer.MAX_VALUE;
            }
        }
        time[1][2] = 3;
        cost[1][2] = 2;
        time[1][4] = 5;
        cost[1][4] = -7;
        time[2][3] = 2;
        cost[2][3] = 5;
        time[4][2] = 1;
        cost[4][2] = 1;

        // 2.初始化各标记节点
        labels.add(new Label(0, 0, 0));
        labels.add(new Label(1, 0, 0)); // 节点1
        labels.add(new Label(2, 3, 10)); // 节点2
        labels.add(new Label(3, 4, 6)); // 节点3
        labels.add(new Label(4, 4, 10)); // 节点4
        labels.get(1).setCost(0);
        labels.get(1).setTime(0);

        // 3.初始化PQ
        P = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            P.add(new ArrayList<Label>());
        }
        Q = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            Q.add(new ArrayList<Label>());
        }

        // 4.先把节点1放进去，因为要从第一个点开始出法
        Q.get(1).add(new Label(labels.get(1)));
    }

    // 判断是否还有可以进行T标号的点，并且将这些点加入到T集合中
    public static boolean buildT() {
        T.clear();
        for (int i = 1; i <= n; i++) {
            // 其实这里说不出来什么所以然
            for (int j = P.get(i).size(); j < Q.get(i).size(); j++) {
                T.add(Q.get(i).get(j));
            }
        }
        if (T.size() == 0) {
            return false;
        } else {
            System.out.println("***********************************");
            for (int i = 0; i < T.size(); i++) {
                System.out.println(T.get(i).toString());
            }
            return true;
        }
    }

    // 找出T集合中最小的label
    public static Label min_label() {
        Label min = new Label();
        min.setTime(Integer.MAX_VALUE);
        for (int i = 0; i < T.size(); i++) {
            if (T.get(i).getTime() < min.getTime() || (T.get(i).getTime() == min.getTime() && T.get(i).getCost() < min.getCost())) {
                min = T.get(i);
            }
        }
        return new Label(min);
    }

    /**
     * 名义上的剪支。假设 next.id = a。
     * 对于节点a，next标记是否在time和cost方面完全劣势于Q.get(a)中已有的标记。
     */
    public static boolean EFF(Label next) {
        boolean is_dominated = false;
        for (int i = 0; i < Q.get(next.getId()).size(); i++) {
            // 如果计算出的这个next与Q中现有的到达next.getId()的节点比较，劣势。所以这个点后面的路线可以剪支，不再进行考虑
            if (next.getTime() > Q.get(next.getId()).get(i).getTime() && next.getCost() > Q.get(next.getId()).get(i).getCost()) {
                is_dominated = true;
                break;
            }
        }
        // 返回的结果为，需不需要这个节点加入到Q集合中
        return !is_dominated;
    }

    // 将label的Q标号，标记为P标号
    public static void treatable(Label l) {
        // 理解为，通过一个新的P标号，来扩展Q标号
        for (int successor = 1; successor <= n; successor++) {
            if (cost[l.getId()][successor] != Integer.MAX_VALUE) { // 如果此路径可行
                if (l.getTime() + time[l.getId()][successor] < labels.get(successor).getEnd()) { // 如果满足时间窗约束
                    // 假设从 label l 扩展出来的 label 为 next
                    Label next = new Label(labels.get(successor));
                    next.setTime((l.getTime() + time[l.getId()][successor]) > next.getStart() ? (l.getTime() + time[l.getId()][successor]) : next.getStart());
                    next.setCost(l.getCost() + cost[l.getId()][successor]);
                    next.setI(l.getId());
                    next.setJ(P.get(l.getId()).size());
                    // 判断next标记是否可以加入到Q标记中
                    if (EFF(next)) {
                        Q.get(next.getId()).add(next);
                    }
                }
            }
        }
        // 为节点l.getId() 添加一个P标号
        P.get(l.getId()).add(l);
    }
}